Caractéristiques d'un graphe

Un réseau social, comprenant des personnes et des liens (contacts, amitiés, etc.), peut être représenté par un graphe. 

Un sommet représente une personne. Un trait représente un lien (d'amitié, par exemple).

Définitions (avec les exemples en italique)

• La distance entre deux sommets est la longueur de la plus petite chaîne qui les relie. Elle se compte en nombre de traits (de liens). Ex. : la distance entre Luc et Louna est de 3 car il y a trois traits entre Luc et Louna au minimum ; la distance entre Margot et Florian est également de 3 (en passant par Gabriel et Luc). Dans chacun de ces cas, on doit parcourir au minimum trois traits pour relier ces personnes. 
• L’excentricité d’un sommet est la distance maximale entre ce sommet et les autres sommets du graphe. Ex. : l'excentricité de Luc est 5 car c’est Liam qui est à la plus grande distance de lui, et cette distance est 5 ; l'excentricité d'Ethan est aussi 5 car Hugo et Louna sont à la plus grande distance de lui, et cette distance est 5.  
• Le centre d’un graphe est le sommet dont l’excentricité est la plus petite. Il peut y avoir plusieurs centres dans un graphe. Ici, Elise, Maelys et Margot sont les centres (avec chacun une excentricité de 4). 
• Le rayon d’un graphe est l’excentricité du centre du graphe (ou de l’un des centres s’il y en a plusieurs). Ici, le rayon est 4 puisque l'excentricité des centres est 4. 
• Le diamètre d’un graphe est  la distance maximale entre deux sommets de ce graphe. Ici, les deux personnes les plus éloignées sont Liam et Hugo (distance 7) ou Liam et Louna (distance 7). Le diamètre du graphe est donc 7.